/*
 * $Id: GarbageFreeFormatterUtils.java 139 2013-01-25 06:35:42Z vladimirow@mail.ru $
 * $HeadURL: http://ultralog.googlecode.com/svn/ultralog/tags/release-0.1/src/java/com/google/code/ultralog/formatter/gfree/GarbageFreeFormatterUtils.java $
 *
 * This file is a part of ultralog project (http://code.google.com/p/ultralog/).
 * Released under New BSD License.
 */
package com.google.code.ultralog.formatter.gfree;

import java.util.Arrays;

import com.google.code.ultralog.utils.CharacterOutputStream;

/**
 * Contains various useful methods that simplify implementation of garbage-free
 * formatters.
 *
 * @author Mikhail Vladimirov
 */
public class GarbageFreeFormatterUtils
{
    private final static int [] DIGITS = new int [10000];

    static
    {
        for (int i = 0; i < 10000; i++)
        {
            DIGITS [i] =
                (('0' + i / 1000 % 10) << 24) +
                (('0' + i / 100 % 10) << 16) +
                (('0' + i / 10 % 10) << 8) +
                (('0' + i / 1 % 10) << 0);
        }
    }

    private final static int [] POW_10 = new int [258];

    static
    {
        for (int i = 0; i < 258; i++)
            POW_10 [i] = (int)Math.pow (10.0, Math.scalb (i, -8));
    }

    private final static int BUFFER_SIZE = 20;

    private final static ThreadLocal <char []> CHAR_BUFFER =
        new ThreadLocal <char[]> ()
        {
            @Override
            protected char[] initialValue ()
            {
                return new char [BUFFER_SIZE];
            }
        };

    /**
     * Write integer value in decimal format to given character output stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeInteger (int value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (value == Integer.MIN_VALUE)
            output.write ("-2147483648", 0, 11);
        else if (value == 0)
            output.write ('0');
        else
        {
            boolean sign = value < 0;
            value = Math.abs (value);

            char [] buffer = CHAR_BUFFER.get ();
            int pos = BUFFER_SIZE;

            while (value >= 10000)
            {
                int v = value / 10000;
                int d = value - v * 10000;
                value = v;

                int d4 = DIGITS [d];

                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
            }

            int d4 = DIGITS [value];

            if (value >= 1)
                buffer [--pos] = (char)((d4 >>> 0) & 0xFF);

            if (value >= 10)
                buffer [--pos] = (char)((d4 >>> 8) & 0xFF);

            if (value >= 100)
                buffer [--pos] = (char)((d4 >>> 16) & 0xFF);

            if (value >= 1000)
                buffer [--pos] = (char)((d4 >>> 24) & 0xFF);

            if (sign)
                buffer [--pos] = '-';

            output.write (buffer, pos, BUFFER_SIZE - pos);
        }
    }

    /**
     * Write long value in decimal format to given character output stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeLong (long value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (value == Long.MIN_VALUE)
            output.write ("-9223372036854775808", 0, 20);
        else if (value == 0L)
            output.write ('0');
        else
        {
            boolean sign = value < 0;
            value = Math.abs (value);

            char [] buffer = CHAR_BUFFER.get ();
            int pos = getChars (value, buffer);

            if (sign)
                buffer [--pos] = '-';

            output.write (buffer, pos, BUFFER_SIZE - pos);
        }
    }

    /**
     * Write float value in simple decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeFloat (float value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeFloat (value, output, false);
    }

    /**
     * Write float value in scientific decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeFloatScientific (
        float value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeFloat (value, output, true);
    }

    /**
     * Write double value in simple decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeDouble (double value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeDouble (value, output, false);
    }

    /**
     * Write double value in scientific decimal format to given character output
     * stream.
     *
     * @param value value to be written
     * @param output character output stream to write value to
     */
    public static void writeDoubleScientific (
        double value, CharacterOutputStream output)
    {
        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        writeDouble (value, output, true);
    }

    private final static int BUFFER_LENGTH = 81;

    // log_2 (10)
    private final static double EXPONENT_FACTOR =
        3.3219280948873623478703194294894;

    private final static int [] POWER_5 = {
        1, 5, 25, 125, 625, 3125, 15625, 78125, 390625, 1953125, 9765625,
        48828125, 244140625, 1220703125};

    private final static ThreadLocal <int []> BUFFER =
        new ThreadLocal <int []> ()
        {
            @Override
            protected int[] initialValue()
            {
                return new int [BUFFER_LENGTH];
            };
        };

    private static void writeFloat (
        float value, CharacterOutputStream output, boolean scientific)
    {
        if (Float.isNaN (value))
            output.write ("NaN", 0, 3);
        else if (Float.isInfinite (value))
        {
            if (value > 0.0f)
                output.write (
                    "Infinity",
                    0, 8);
            else
                output.write (
                    "-Infinity",
                    0, 9);
        }
        else
        {
            int bits = Float.floatToRawIntBits (value);

            boolean negative = bits >>> 31 != 0;
            int binaryExponent = ((bits >>> 23) & 0xFF) - 150;
            int binaryMantissa = bits & 0x7FFFFF;

            if (binaryExponent == -150) // Subnormal mantissa
                binaryExponent = -149;
            else // Normal mantissa
                binaryMantissa += 0x800000;

            double significantDigits = (binaryExponent - 1) / EXPONENT_FACTOR;
            int decimalExponent = (int)Math.floor (significantDigits);
            int margin = POW_10 [(int)Math.scalb (
                significantDigits - decimalExponent, 8)];

            long decimalMantissa = getDecimalMantissa (
                binaryMantissa, binaryExponent, decimalExponent);

            int lastDigit = (int)(decimalMantissa % 10);

            if (lastDigit <= margin)
            {
                decimalMantissa /= 10;
                decimalExponent += 1;
            }
            else if (lastDigit >= 10 - margin)
            {
                decimalMantissa = decimalMantissa / 10 + 1;
                decimalExponent += 1;
            }

            if (scientific)
                formatScientific (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
            else
                formatSimple (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
        }
    }

    private static void writeDouble (
        double value, CharacterOutputStream output, boolean scientific)
    {
        if (Double.isNaN (value))
            output.write ("NaN", 0, 3);
        else if (Double.isInfinite (value))
        {
            if (value > 0.0f)
                output.write (
                    "Infinity",
                    0, 8);
            else
                output.write (
                    "-Infinity",
                    0, 9);
        }
        else
        {
            long bits = Double.doubleToRawLongBits (value);

            boolean negative = bits >>> 63 != 0;
            int binaryExponent = (int)((bits >>> 52) & 0x7FF) - 1075;
            long binaryMantissa = bits & 0xFFFFFFFFFFFFFL;

            if (binaryExponent == -1075) // Subnormal mantissa
                binaryExponent = -1074;
            else // Normal mantissa
                binaryMantissa += 0x10000000000000L;

            double significantDigits = (binaryExponent - 1) / EXPONENT_FACTOR;
            int decimalExponent = (int)Math.floor (significantDigits);
            int margin = POW_10 [(int)Math.scalb (
                significantDigits - decimalExponent, 8)];

            long decimalMantissa = getDecimalMantissa (
                binaryMantissa, binaryExponent, decimalExponent);

            int lastDigit = (int)(decimalMantissa % 10);

            if (lastDigit <= margin)
            {
                decimalMantissa /= 10;
                decimalExponent += 1;
            }
            else if (lastDigit >= 10 - margin)
            {
                decimalMantissa = decimalMantissa / 10 + 1;
                decimalExponent += 1;
            }

            if (scientific)
                formatScientific (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
            else
                formatSimple (negative, decimalMantissa,
                    decimalMantissa == 0 ? 0 : decimalExponent, output);
        }
    }

    private static void formatSimple (
            boolean negative, long decimalMantissa, int decimalExponent,
            CharacterOutputStream output)
    {
        if (decimalMantissa < 0)
            throw new IllegalArgumentException (
                "Decimal mantissa (" + decimalMantissa + ") < 0");

        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        if (negative)
            output.write ('-');

        if (decimalMantissa == 0)
            output.write ("0.0", 0, 3);
        else
        {
            if (decimalExponent >= 0)
            {
                writeLong (decimalMantissa, output);
                writeCharacterNTimes ('0', decimalExponent, output);
                output.write (".0", 0, 2);
            }
            else // decimalExponent < 0
            {
                char [] buffer = CHAR_BUFFER.get ();
                int pos = getChars (decimalMantissa, buffer);

                int afterLastDigitPos = BUFFER_SIZE;

                for (int i = BUFFER_SIZE - 1; buffer [i] == '0'; i--)
                    afterLastDigitPos = i;

                int n = BUFFER_SIZE - pos;

                if (n <= -decimalExponent) // No significant digits before dot
                {
                    output.write ("0.", 0, 2);
                    writeCharacterNTimes ('0', -decimalExponent - n, output);
                    output.write (buffer, pos, afterLastDigitPos - pos);
                }
                else
                {
                    int digitsBeforeDot = n + decimalExponent;
                    int digitsAfterDot =
                        afterLastDigitPos - pos - digitsBeforeDot;

                    output.write (buffer, pos, digitsBeforeDot);
                    output.write ('.');

                    if (digitsAfterDot > 0)
                        output.write (
                            buffer, pos + digitsBeforeDot, digitsAfterDot);
                    else
                        output.write ('0');
                }
            }
        }
    }

    private static void formatScientific (
            boolean negative, long decimalMantissa, int decimalExponent,
            CharacterOutputStream output)
    {
        if (decimalMantissa < 0)
            throw new IllegalArgumentException (
                "Decimal mantissa (" + decimalMantissa + ") < 0");

        if (output == null)
            throw new IllegalArgumentException ("Output is null");

        int n;

        if (decimalMantissa == 0)
            n = 1;
        else if (decimalMantissa >= 100000000000000000L)
            n = 18;
        else if (decimalMantissa <= Integer.MAX_VALUE)
        {
            int dm = (int)decimalMantissa;

            if (dm >= 1000000000)
                n = 10;
            else
            {
                int k = 1;
                n = 0;

                while (dm >= k)
                {
                    n += 1;
                    k *= 10;
                }
            }
        }
        else
        {
            long k = 1L;
            n = 0;

            while (decimalMantissa >= k)
            {
                n += 1;
                k *= 10;
            }
        }

        n -= 1;

        formatSimple (negative, decimalMantissa, - n, output);

        output.write ('e');

        writeInteger (decimalMantissa == 0 ? 0 : (decimalExponent + n), output);
    }

    private static long getDecimalMantissa (
        long binaryMantissa, int binaryExponent, int decimalExponent)
    {
        if (binaryMantissa < 0)
            throw new IllegalArgumentException (
                "Binary mantissa (" + binaryMantissa + ") < 0");

        if (binaryExponent < -1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") < -1075");

        if (binaryExponent > 1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") > 1075");

        if (binaryExponent == 0)
            return getDecimalMantissa0 (binaryMantissa, decimalExponent);
        else if (binaryExponent > 0)
            return getDecimalMantissaPlus (
                binaryMantissa, binaryExponent, decimalExponent);
        else // binaryExponent < 0
            return getDecimalMantissaMinus (
                binaryMantissa, binaryExponent, decimalExponent);
    }

    private static long getDecimalMantissa0 (
        long binaryMantissa, int decimalExponent)
    {
        if (binaryMantissa < 0)
            throw new IllegalArgumentException (
                "Binary mantissa (" + binaryMantissa + ") < 0");

        if (decimalExponent == 0)
            return binaryMantissa;
        else if (decimalExponent > 0)
        {
            long result = binaryMantissa;
            for (int i = 0; i < decimalExponent; i++)
                result /= 10;
            return result;
        }
        else // decimalExponent < 0
        {
            long result = binaryMantissa;
            for (int i = 0; i > decimalExponent; i--)
                result *= 10;
            return result;
        }
    }

    private static long getDecimalMantissaPlus (
        long binaryMantissa, int binaryExponent, int decimalExponent)
    {
        if (binaryMantissa < 0)
            throw new IllegalArgumentException (
                "Binary mantissa (" + binaryMantissa + ") < 0");

        if (binaryExponent <= 0)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") <= 0");

        if (binaryExponent > 1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") > 1075");

        int [] buffer = BUFFER.get ();
        int pos = binaryExponent / 32;
        int offset = binaryExponent % 32;
        int l;

        if (offset > 0)
        {
            buffer [pos + 2] = (int)(binaryMantissa >>> (64 - offset));
            l = pos + 3;
        }
        else l = pos + 2;

        buffer [pos + 1] = (int)(binaryMantissa >>> (32 - offset));
        buffer [pos] = (int)(binaryMantissa << offset);

        Arrays.fill (buffer, 0, pos, 0);

        return normalizeDecimalMantissa (buffer, l, decimalExponent);
    }

    private static long getDecimalMantissaMinus (
        long binaryMantissa, int binaryExponent, int decimalExponent)
    {
        if (binaryMantissa < 0)
            throw new IllegalArgumentException (
                "Binary mantissa (" + binaryMantissa + ") < 0");

        if (binaryExponent < -1075)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") < -1075");

        if (binaryExponent >= 0)
            throw new IllegalArgumentException (
                "Binary exponent (" + binaryExponent + ") >= 0");

        int be = binaryExponent;

        while (binaryMantissa <= Long.MAX_VALUE / 5 && be < 0)
        {
            binaryMantissa *= 5;
            be += 1;
        }

        int [] buffer = BUFFER.get ();
        buffer [0] = (int)binaryMantissa;
        buffer [1] = (int)(binaryMantissa >>> 32);

        int l = mulPower5 (buffer, buffer [1] == 0 ? 1 : 2, -be);

        return normalizeDecimalMantissa (
            buffer, l, decimalExponent - binaryExponent);
    }

    /**
     * Multiply given big integer by power of 5.
     *
     * @param buffer buffer containing big integer
     * @param length length of big integer
     * @param power power of 5 to multiply by
     * @return result big integer length
     */
    private static int mulPower5 (int [] buffer, int length, int power)
    {
        if (buffer == null)
            throw new IllegalArgumentException ("Buffer is null");

        if (length < 0)
            throw new IllegalArgumentException ("Length (" + length +") < 0");

        if (power < 0)
            throw new IllegalArgumentException ("Power (" + power + ")< 0");

        int maxStep = POWER_5.length - 1;
        while (power > 0)
        {
            int step = Math.min (power, maxStep);
            int k = POWER_5 [step];

            int carry = 0;
            for (int j = 0; j < length; j++)
            {
                long chunk =
                    (((long)buffer [j]) & 0xFFFFFFFFL) * k +
                    (((long)carry) & 0xFFFFFFFFL);

                buffer [j] = (int)chunk;
                carry = (int)(chunk >>> 32);
            }

            if (carry != 0)
                buffer [length++] = carry;

            power -= step;
        }

        return length;
    }

    private static long normalizeDecimalMantissa (
        int [] buffer, int length, int decimalExponent)
    {
        if (buffer == null)
            throw new IllegalArgumentException ("Buffer is null");

        if (length < 0)
            throw new IllegalArgumentException ("Length (" + length + ") < 0");

        int bufferLength = buffer.length;
        if (length > buffer.length)
            throw new IllegalArgumentException (
                "Length (" + length + ") > buffer length (" +
                bufferLength + ")");

        if (decimalExponent >= 0)
        {
            length = shiftRight (buffer, length, decimalExponent);

            return divPower5 (
                buffer, length, decimalExponent);
        }
        else
        {
            long result;

            if (length == 0)
                result = 0L;
            else if (length == 1)
                result = ((long)buffer [0]) & 0xFFFFFFFFL;
            else if (length == 2)
                result =
                    (((long)buffer [1]) << 32 |
                    (((long)buffer [0]) & 0xFFFFFFFFL));
            else throw new Error ("Mantissa does not fit into long");

            for (int i = 0; i > decimalExponent; i--)
                result *= 10;

            return result;
        }
    }

    private static int shiftRight (int [] buffer, int length, int n)
    {
        if (buffer == null)
            throw new IllegalArgumentException ("Buffer is null");

        if (length < 0)
            throw new IllegalArgumentException ("Length (" + length + ") < 0");

        if (n < 0)
            throw new IllegalArgumentException ("N (" + n + ") is null");

        int bufferLength = buffer.length;
        if (length > bufferLength)
            throw new IllegalArgumentException (
                "Length (" + length + ") > buffer lenght (" +
                bufferLength + ")");

        if (n >= length * 32)
        {
            length = 0;
        }
        else if (n > 0)
        {
            int offset = n / 32;
            int bitOffset = n % 32;

            if (bitOffset == 0)
            {
                length -= offset;
                for (int i = 0; i < length; i++)
                    buffer [i] = buffer [i + offset];
            }
            else
            {
                length -= offset;
                int l1 = length - 1;
                for (int i = 0; i < l1; i++)
                {
                    buffer [i] =
                        buffer [i + offset] >>> bitOffset |
                        buffer [i + offset + 1] << (32 - bitOffset);
                }

                buffer [l1] =
                buffer [l1 + offset] >>> bitOffset;
            }
        }

        while (length > 0 && buffer [length - 1] == 0)
            length -= 1;

        return length;
    }

    /**
     * Divide given big integer by given power of 5.
     *
     * @param buffer big integer to divide
     * @param length length of big integer to be divided
     * @param power power of 5 to divide by
     * @return division result
     */
    private static long divPower5 (int [] buffer, int length, int power)
    {
        int maxStep = POWER_5.length - 1;
        while (power > 0 && (length > 2 || (length == 2 && buffer [1] < 0L)))
        {
            int step = Math.min (power, maxStep);
            int k = POWER_5 [step];

            int carry = 0;
            for (int j = length - 1; j >= 0; j--)
            {
                long chunk =
                    (((long)carry) << 32) +
                    (((long)buffer [j]) & 0xFFFFFFFFL);

                int v = (int)(chunk / k);

                buffer [j] = v;
                carry = (int)(chunk - ((long)v) * k);

                if (v == 0 && j == length - 1)
                    length -= 1;
            }

            power -= step;
        }

        long result;

        if (length == 0)
            result = 0L;
        else if (length == 1)
            result = ((long)buffer [0]) & 0xFFFFFFFFL;
        else if (length == 2)
            result =
                (((long)buffer [1]) << 32 |
                (((long)buffer [0]) & 0xFFFFFFFFL));
        else
            throw new IllegalArgumentException (
                "Result does not fit into long");

        while (power > 0 && result != 0)
        {
            int step = Math.min (power, maxStep);
            int k = POWER_5 [step];

            result /= k;
            power -= step;
        }

        return result;
    }

    private static int getChars (long value, char [] buffer)
    {
        if (value < 0)
            throw new IllegalArgumentException ("Value (" + value + ") < 0");

        if (buffer == null)
            throw new IllegalArgumentException ("Buffer is null");

        int pos = BUFFER_SIZE;

        while (value > Integer.MAX_VALUE)
        {
            long v = value / 10000;
            int d = (int)(value - v * 10000);
            value = v;

            int d4 = DIGITS [d];

            buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
        }

        int intValue = (int)value;

        while (intValue >= 10000)
        {
            int v = intValue / 10000;
            int d = intValue - v * 10000;
            intValue = v;

            int d4 = DIGITS [d];

            buffer [--pos] = (char)((d4 >>> 0) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 8) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 16) & 0xFF);
            buffer [--pos] = (char)((d4 >>> 24) & 0xFF);
        }

        int d4 = DIGITS [intValue];

        if (intValue >= 1)
            buffer [--pos] = (char)((d4 >>> 0) & 0xFF);

        if (intValue >= 10)
            buffer [--pos] = (char)((d4 >>> 8) & 0xFF);

        if (intValue >= 100)
            buffer [--pos] = (char)((d4 >>> 16) & 0xFF);

        if (intValue >= 1000)
            buffer [--pos] = (char)((d4 >>> 24) & 0xFF);

        return pos;
    }

    private static void writeCharacterNTimes (
            char ch, int n, CharacterOutputStream output)
   {
       if (n < 0) throw new IllegalArgumentException ("N < 0");

       if (output == null)
           throw new IllegalArgumentException ("Output is null");

       while (n > 0)
       {
           switch (n)
           {
           case 1:
               output.write (ch);
               n -= 1;
               break;
           case 2:
               output.write (ch, ch);
               n -= 2;
               break;
           case 3:
               output.write (ch, ch, ch);
               n -= 3;
               break;
           default:
               output.write (ch, ch, ch, ch);
               n -= 4;
               break;
           }
       }
   }
}
